// 1795.[单源最短路径Dijkstra优先队列BFS邻接矩阵]最佳路径
// https://oj.rnd.huawei.com/problems/1795/details
// 给定单板间的有向连接关系：如单板101到单板102存在连接，权值为10，
// 其连接关系描述为：101 102 10;
// 单板102到单板101存在连接，权值为6，其连接关系描述为：102 101 6。
// 基于单板间的有向连接关系，从起始单板到目的单板可能有0或多条可达的有向路径，
// 某条路径权值是该路径上各连接的权值之和。
// 给定多组格式为起始单板 目的单板的查询命令，请依次计算并返回其最佳路径权值；
// 若某条最佳路径不存在，则该条最佳路径权值返回-1。
// 最佳路径的规则如下：经过的连接个数最少；
// 若符合规则 1 的路径存在多条，选择权值最小的；
// Dijkstra 算法是(Single Source Shortest Path) 问题的算法，
// 但它有一个巨大的限制：只能用于没有权重为负的边的图。
// 若符合规则 1 的路径存在多条，选择权值最小的；(节点最少，权值最小)
//输入 2 2
// 100 101 10
// 102 101 5
// 100 101
// 102 100
//输出 10
//-1

// 25 5
// 100 101 10
// 100 102 10
// 100 103 1
// 100 104 10
// 100 105 10
// 103 100 1
// 103 101 20
// 103 102 20
// 103 104 20
// 103 105 20
// 104 204 15
// 105 203 5
// 200 100 15
// 201 103 5
// 203 200 8
// 203 201 8
// 203 202 8
// 203 205 8
// 203 204 2
// 204 200 18
// 204 201 18
// 204 202 18
// 204 203 5
// 204 205 18
// 205 206 18
// 203 204
// 204 203
// 100 206
// 204 100
// 206 100
// --
// 2
// 5
// 41
// 33
//-1

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

const static int VALUE_MAX = 0x3fffffff;
#define BOARD_ID 0
#define BOARD_COUNT 1
#define BOARD_WT 2

#define NEXT_ID 0
#define NEXT_WT 1

typedef tuple<int, int, int>
    Board;                      // tuple<curNode, count, weight>   // vertex
typedef pair<int, int> FromTo;  // <from, to>
typedef pair<int, int> ToNode;  // <to, weight>

struct Cmp_Greater {
  bool operator()(const Board& pa1, const Board& pa2) const {
    if (get<BOARD_COUNT>(pa1) == get<BOARD_COUNT>(pa2)) {
      return get<BOARD_WT>(pa1) > get<BOARD_WT>(pa2);
    }
    return get<BOARD_COUNT>(pa1) > get<BOARD_COUNT>(pa2);
  }
};

// connection : b1 -> b2 = weight
// route : src -> dst
int getOneBestRoute(const vector<vector<int>>& connection,
                    const FromTo& route) {
  int route_from = route.first;
  int route_end = route.second;
  priority_queue<Board, vector<Board>, Cmp_Greater>
      queNode;                          // order by count 1,2,3
  map<int, set<ToNode>> mapConnection;  // from, toList<toId, weight>
  set<FromTo> stVisited;                // <from, to> = isVisited
  // 保存连接关系到 mapConnection
  for (auto conn : connection) {
    int from = conn[0];
    int to = conn[1];
    int weight = conn[2];
    // 起始点进队列,count=1
    if (route_from == from) {
      queNode.push({to, 1, weight});
      stVisited.insert({from, to});
    }
    mapConnection[from].insert({to, weight});
  }
  int res_count = VALUE_MAX;
  int res_wtTotal = VALUE_MAX;
  while (!queNode.empty()) {
    // printf("\n\nque.size=%d\n", queNode.size());
    Board node = queNode.top();
    queNode.pop();
    int curNode = get<BOARD_ID>(node);
    int count = get<BOARD_COUNT>(node);
    int weightSum = get<BOARD_WT>(node);
    // 出队列的是路径终点
    if (route_end == curNode) {
      if (count < res_count) {
        res_count = count;
        res_wtTotal = weightSum;
      } else if (res_count == count) {
        res_wtTotal = min(res_wtTotal, weightSum);
      }
      continue;
    }
    // 遍历寻找当前节点的下一个节点
    for (auto next : mapConnection[curNode]) {
      int nextNode = get<NEXT_ID>(next);
      if (stVisited.count({curNode, nextNode}) == 0) {
        queNode.push({nextNode, count + 1, weightSum + get<NEXT_WT>(next)});
        stVisited.insert({curNode, nextNode});
      }
    }
  }
  return res_wtTotal == VALUE_MAX ? -1 : res_wtTotal;
}

// connection : b1 -> b2 = weight
// route : src -> dst
vector<int> GetBestRoute(const vector<vector<int>>& connection,
                         const vector<vector<int>>& routes) {
  vector<int> vtBest;
  for (auto rt : routes) {
    vtBest.push_back(getOneBestRoute(connection, {rt[0], rt[1]}));
  }
  return vtBest;
}

// ========================================
// 以下为考题输入输出框架，此部分代码不建议改动
int main_1795() {
  int n, m;
  cin >> n >> m;
  int board1, board2, weight;
  vector<vector<int>> connections(n, vector<int>(3, 0));
  for (int loop = 0; loop < n; loop++) {
    cin >> board1 >> board2 >> weight;
    connections[loop][0] = board1;
    connections[loop][1] = board2;
    connections[loop][2] = weight;
  }

  vector<vector<int>> routes(m, vector<int>(2, 0));
  for (int loop = 0; loop < m; loop++) {
    cin >> board1 >> board2;
    routes[loop][0] = board1;
    routes[loop][1] = board2;
  }

  vector<int> res = GetBestRoute(connections, routes);
  for (auto r : res) {
    cout << r << endl;
  }

  return 0;
}
